package pers.qianyu.month_202012.date_20201209;

import org.junit.*;

import java.util.*;

/**
 * 773. 滑动谜题
 * https://leetcode-cn.com/problems/sliding-puzzle/
 *
 * @author mizzle rain
 * @date 2020-12-09 17:17
 */
public class SlidingPuzzle2 {
    /**
     * 优化版本
     * - 使用字符串代替数组
     * - 使用哈希表（数组）存储相邻位置
     */
    public int slidingPuzzle(int[][] board) {
        String target = "123450";
        StringBuilder builder = new StringBuilder();
        for (int[] a : board) {
            for (int b : a) {
                builder.append(b);
            }
        }
        // dict[i] 表示 i 元素的相邻元素的位置
        int[][] dict = {
                {1, 3},
                {0, 2, 4},
                {1, 5},
                {0, 4},
                {1, 3, 5},
                {2, 4},
        };
        String s1 = builder.toString();
        Queue<String> q = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        int step = 0;
        q.add(s1);
        visited.add(s1);
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                String s = q.poll();
                if (s.equals(target)) {
                    return step;
                }
                int index0 = s.indexOf('0');
                int[] neighbor = dict[index0];
                for (int k = 0; k < neighbor.length; k++) {
                    StringBuilder b = new StringBuilder(s);
                    b.setCharAt(index0, b.charAt(neighbor[k]));
                    b.setCharAt(neighbor[k], '0');
                    if (!visited.contains(b.toString())) {
                        visited.add(b.toString());
                        q.offer(b.toString());
                    }
                }
            }
            step++;
        }
        return -1;
    }

    @Test
    public void test1() {
        int[][] arr = {{1, 2, 3}, {4, 0, 5}};
        int result = new SlidingPuzzle2().slidingPuzzle(arr);
        System.out.println("result = " + result);
    }
}
